1. Field of the Invention
The present invention relates to methods for detecting a present position of a vehicle and, more particularly, relates to detecting the vehicle position in an on-vehicle navigation system.
2. Description of the Related Art
An on-vehicle navigation system provides guidance for the driver of the vehicle to make it easier for the driver to arrive at his desired destination. In such a navigation system, the position of the vehicle is detected and map data at the vicinity of the vehicle position is read from a CD-ROM. The resulting map image is stored in a video RAM and a vehicle position mark is superimposed on a predetermined position on the map image. The image in the video RAM is output to a CRT display as a picture signal. As the current position changes with the movement of the vehicle, the vehicle position mark on the screen moves, or the vehicle position mark is fixed at the center of the screen while the map is scrolled, so that the map in the vicinity of the vehicle position can be viewed at all times.
The map data stored in the CD-ROM is divided into regions of suitable longitudinal and latitudinal widths corresponding to a reduced scale. Roads are each indicated by a set of vertices (nodes) which are represented by longitude-latitude coordinates. A road portion connecting two nodes is referred to herein as a "link". The road data contained in each map, as shown in FIG. 17, includes a road list RDLT, a node table NDTB and a crossing constituting node list CRLT. Of these, the road list RDLT contains, for each road, data for: the number of all the nodes on that road; the ordinal number on the node table NDTB of each of the nodes forming a link; the road width between the respective nodes; the speed limit between the respective nodes; traffic control flags between the nodes; the name of the road; the type of the road; etc. Data for road width, speed limit and traffic control as shown in FIG. 18 are the information concerning the link which connects the relevant node to the next node. The traffic control data consists of two bits, where the high order bit is "1" when traveling from that node to the next node is prohibited, while it is "0" when permitted. The low order bit is set to "1" when traveling from the next node to that node is prohibited, while it is set to "0" when permitted.
Further, the crossing constituting node list CRLT contains data for: a set of ordinal numbers, for each crossing in the map, on the node table NDTB of the nodes (referred to as crossing constituting nodes) at the other ends of the links which are connected to the crossing; and crossing traffic control data for indicating whether traveling from one crossing constituting node toward another crossing constituting node by way of the relevant crossing is regulated or not. Eight bits are assigned to each crossing constituting node as the crossing traffic control data. As shown in FIG. 19, in the "i"th (i=1 to 8) crossing traffic control data, the MSB (most significant bit) is set to "1" when traffic on the route from the "i"th crossing constituting node to the first crossing constituting node by way of the relevant crossing is prohibited, while it is set to "0" when permitted. The 2SB (second significant bit) is set to "1" when traffic on the route from the "i"th crossing constituting node to a second crossing constituting node by way of the relevant crossing is prohibited while it is set to "0" when permitted. Likewise, the nSB (nth significant bit) is set to "1" when traffic on the route from the "i"th crossing constituting node toward "n"th crossing constituting node by way of the relevant crossing is prohibited, while it is set to "0" when permitted. Accordingly, the LSB (least significant bit) is set to "1" when traffic on the route from the "i"th crossing constituting node toward the 8th crossing constituting node by way of the relevant crossing is prohibited, while it is set to "0" when permitted.
The node table NDTB is the list of all the nodes on the map. It contains, for each node: coordinate information (longitude-latitude); a crossing identification flag as to whether the node is a crossing or not; a pointer for pointing a location on the crossing constituting node list if it is a constituent of a crossing or for pointing a road to which the node (simple node) belongs if it is not a crossing; etc.
A known on-vehicle navigation system is provided with a route guiding function for guiding on the optimal route from a start point to a destination. In such route guiding, upon setting of a start point and a destination by the driver prior to the start of travel, the map data in the CD-ROM is looked up to perform a simulation calculation, for example, by means of the well known Dijkstra method or breadth first search. (See e.g. related and copending U.S. patent application Ser. No. 08/139,595, filed Oct. 19, 1993, docket no. ALPN-005, incorporated by reference.) For example, the optimal guided route for connecting the start point and the destination with a least traveling distance is obtained, and guided route data combining a node sequence forming the guided route, the start point data at the top and the destination data at the bottom is stored in a guide route memory.
Then, during travel, the node sequence in the guide route memory is searched for the guided route which is contained in the map area on the screen. The guide route is indicated for example by a thick line in a different color from the other roads, so that it is easy for the driver to see which one of the roads should be taken to arrive at his destination.
A known type of such an on-vehicle navigation system having a route guiding function uses map data during route guiding to detect a link where the vehicle is located currently (existing link) which is compared with the guide route data to monitor whether the vehicle has deviated from the guide route. If such a deviation has occurred, a warning message is displayed on the screen to warn the driver so that he may take steps to return to his desired route.
Also, there is a known system providing a route guide for the driver, for example, by displaying on a part of the screen a guide image for traveling through a crossing, where the structure of the crossing and the course to be taken toward the destination are indicated with respect to the crossing on the guide route ahead of the vehicle in its travel direction of travel. In such a system, the existing link and the guide route data are collated to determine whether the vehicle has traveled through the crossing which is currently the subject of guiding. If the crossing has been passed, the crossing guide image is switched to that of the next crossing on the guided route.
In the detection method of the existing link in such a conventional on-vehicle navigation system, supposing that the vehicle position D and the nearby links i are located as shown in FIG. 20, map matching based on a projection method is performed by looking up map data to find link g which is closest to the vehicle position D. Link g is then set as the existing link. In some cases, however, the vehicle actually is located on a link other than the link g due to a detection error of the vehicle position D or data error in forming the map data. The prior art systems suffer from erroneous determination of deviation from the guided route and of passing a crossing (cross road) which is a subject of the route guiding.